package warm100;

import utils.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class pathSum_437 {
    public int pathSum(TreeNode root, int targetSum) {
        //想法是递归回溯，得到左右节点中含有的路径数
        //回溯需要返回的前缀和太多
        //故从根节点向下，遍历实时前缀和
        map.put(0L, 1);
        find(root, targetSum, 0L);
        return ans;
    }

    int ans = 0;
    //记录各种值前缀分别出现的次数
    HashMap<Long, Integer> map = new HashMap<>();

    public void find(TreeNode root, long targetSum, Long sum) {
        if (root == null) return;
        Long s = sum + root.val;  //更新前缀和
        //增加前缀和，即左子树和右子树分别加当前val值
        //targetSum != 0，那么 ans += cnt[s - targetSum] 和 cnt[s] += 1 这两行代码井水不犯河水，先执行谁都是可以的
        ans += map.getOrDefault(s - targetSum, 0);  //寻找是否有对应的前缀和
        map.merge(s, 1, Integer::sum);  //保存当前前缀和，没有则设为1，有则s+1
        find(root.left, targetSum, s);
        find(root.right, targetSum, s);
        //关键步骤
        // 路径走完，剪枝，防止对其他产生影响
        map.merge(s, -1, Integer::sum);  //数量设为 s-1
    }
}
